1. Field of the Invention
The present invention relates to a routing switch for constructing an interconnection network of a parallel processing computer, and more particularly, to a crossbar routing switch for constructing a hierarchical crossbar interconnection network which can be easily expanded in a parallel processing computer performing a high speed parallel processing based on clusters.
2. Description of the Related Art
A parallel processing computer consists of a plurality of processing nodes, and an interconnection network which interconnects the plurality of processing nodes to provide data paths therebetween. The interconnection network, which is an essential part of the parallel processing computer, is an important factor in determining the architecture and performance of the parallel processing computer. The interconnection network should provide an efficient way of interconnection and an expansibility for interconnecting a lot of processing nodes.
A routing switch gives a great deal of influence upon the performance of the overall system because the characteristic of the interconnection network is determined by the characteristic of a routing switch which is one of the elements of the interconnection network. Parallel processing systems have peculiar structural characteristics tailored to their specific applications. The most critical element defining the structural characteristic is a connection architecture, i.e., an interconnection network which interconnects processors within the system.
Most parallel processing systems are constructed in a hierarchical structure and generally consists of 2 or 3 hierarchical layers. The lowest layer consists of a uniprocessor node or Symmetric Multi-Processing (SMP) node. The SMP node has one connection architecture, and is considered as a sub-system which can be independently operated depending on the type of the system. These uniprocessor nodes or SMP nodes are interconnected to form one hierarchical layer which is generally independently operated and is referred to as a "cluster".
A module which defines the structural characteristic of the parallel processing system constructed in a hierarchical structure is a routing switch which forms a interconnection network of a hierarchical structure. Most routing switches have been proposed as having basic features of a crossbar switch. These switches have been used in a communication system as well as in a computer system.
The crossbar switch disclosed by Frank E. Barber, et al. in the article entitled "A 64.times.17 Non-Blocking Crosspoint Switch," IEEE Int'l Solid-State Circuits Conference, pp 116-117, Feb. 18, 1988 is a non-blocking switch commonly used for applications to communications which has 64 inputs and 17 outputs. The crossbar switch disclosed by Hyun J. Shin, et al. in the article entitled "A 250-Mbit/s CMOS Crosspoint Switch," IEEE Journal of Solid-State Circuits Conference, pp 478-486, April 1989 is a high speed switch having 16 inputs and 16 outputs. These switches are a single bit serial transmission switch of a circuit switch type, and these switches use a centralized routing scheme wherein a routing control signal is provided from an external module to determine a data path. These switches are not suitable for most computer systems which use a distributed routing scheme with a packet switch, and are generally used in a communication system of a circuit switch type and the centralized routing scheme.
The interconnection networks and routing switches proposed for use in a parallel processing system or multi-processing system perform a parallel transmission in a unit of byte.
The switching element disclosed in U.S. Pat. No. 4,890,281 (Dec. 26, 1989) to Gian P. Balboni, et al. entitled "Switching Element for Self-Routing Multistage Packet-Switching Interconnection Network" is a routing switch which forms a multistage packet switching interconnection network having a self-routing control capability. This switching element is a packet switch for a multistage interconnection network such as Omega, Delta, Benes interconnection networks which has 2 inputs and 2 outputs. This switching element is characterized in that it resolves a routing conflict generated in an interconnection network by using time information. The switching element devised by Gian P. Balboni, et al. has a drawback that it is not suitable for an interconnection network of a hierarchical structure because it uses a store and forward (SAF) routing control scheme and is used solely for a multistage interconnection network due to the structural constraints.
The switching element disclosed in Korean Patent No. 9,307,017 (Jul. 26, 1993) to S. Kim and K. Lee entitled "Switching Device of Interconnection Network for Preventing Deadlock Using Mesh Network" is a routing switch for preventing a deadlock in a mesh interconnection network which inherently causes a deadlock. The switching element disclosed in European patent application No. 93,113,397.9 filed on Mar. 23, 1993 by Howard T. Olnowich and Arthur R. Williams and entitled "Multiple Torus Switching Apparatus" is a switching element which can enhance the performance of an interconnection network by selecting an optimum path having a small delay time from multipaths between a transmitting node and a receiving node in a Torus-Mesh interconnection network using a conventional Wormhole routing control scheme. The switching elements disclosed by S. Kim, et al. and Howard T. Olnowich are switching elements for use in a mesh interconnection network and a Torus-Mesh interconnection network, respectively, and thus are not suitable for a interconnection network of a hierarchical structure.
Although the Mesh interconnection network and Torus-Mesh interconnection network have excellent expansibility, they are not adequate for a parallel processing system having a hierarchical structure consisting of clusters.
The shunt interconnection network proposed by Steven E. Butner, et al. in the article entitled "A Fault-Tolerant GaAs/CMOS Interconnection Network for Scalable Multiprocessors," IEEE Journal of Solid-State Circuits, pp 692-705, May 1991 is a crossbar interconnection network having a hierarchical structure. This interconnection network is a hierarchical structure of extensibility and a combination of a plurality of switching elements, a plurality of network interface elements, and a controller for controlling the switching elements and network interface elements, and is disadvantageous in that a basic block should be designed several times to extend the data length. In other words, in this interconnection network, the extension of a data length is supported, however for the realization thereof, it is inevitable to re-design a basic block.